//在二维网格 grid 上，有 4 种类型的方格：
//
//
// 1 表示起始方格。且只有一个起始方格。
// 2 表示结束方格，且只有一个结束方格。
// 0 表示我们可以走过的空方格。
// -1 表示我们无法跨越的障碍。
//
//
// 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
//
// 每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
//
//
//
// 示例 1：
//
// 输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
//输出：2
//解释：我们有以下两条路径：
//1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
//2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
//
// 示例 2：
//
// 输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
//输出：4
//解释：我们有以下四条路径：
//1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
//2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
//3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
//4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
//
// 示例 3：
//
// 输入：[[0,1],[2,0]]
//输出：0
//解释：
//没有一条路能完全穿过每一个空的方格一次。
//请注意，起始和结束方格可以位于网格中的任意位置。
//
//
//
//
// 提示：
//
//
// 1 <= grid.length * grid[0].length <= 20
//
//
// Related Topics 位运算 数组与矩阵 回溯与递归 矩阵 👍 232 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function uniquePathsIII(grid: number[][]): number {

    let dfs = (sx, sy, cnt, grid) => {
        //? 不满足条件
        if (!check(sx, sy, grid)) return 0;
        //? 到达终点需要判断空格是否走完
        if (grid[sx][sy] === 2) {
            //? 走到终点时，也要判断一下当前所有空格是否走完
            return cnt === 0 ? 1 : 0;
        }
        //? res记录路径条数
        let res = 0;
        grid[sx][sy] = -1; //? 走过的空格进行标记，设置为障碍即可
        res += dfs(sx + 1, sy, cnt - 1, grid); //? 四个方向进行搜索 这是矩阵上回溯题的关键代码
        res += dfs(sx, sy + 1, cnt - 1, grid);
        res += dfs(sx - 1, sy, cnt - 1, grid);
        res += dfs(sx, sy - 1, cnt - 1, grid);
        grid[sx][sy] = 0; //? 回溯过程，不影响后续dfs
        return res;

    };
    let cnt = 1; //? 统计地图中可走的方格个数，包括终点，故初始值为1
    let sx, sy; //? 记录起点坐标
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            //? 记录起点的位置
            if (grid[i][j] === 1) {
                sx = i;
                sy = j;
            } else if (grid[i][j] === 0) {
                //? 计算可走的空格数
                cnt++;
            }
        }
    }
    return dfs(sx, sy, cnt, grid);
};
//? 剪枝条件
let check = (sx, sy, grid) => {
    if (sx < 0 || sx >= grid.length || sy < 0 || sy >= grid[0].length || grid[sx][sy] == -1)
        return false;
    return true;
};


//leetcode submit region end(Prohibit modification and deletion)
